package leetcode.code0440;

public class SolutionNew {

//	static int[][] tables;
//	static {
//		tables = new int[10][11];
//		int m = tables.length, n = tables[0].length;
//		int cur = 1;
//		for (int i = 1; i < m; i++) {
//			for (int j = 1; j < n; j++) {
//				tables[i][j] = cur;
//			}
//			cur *= 10;
//		}
//	}

	public int findKthNumber(int n, int k) {
		int len = this.len(n);
		int[] high = this.high(n);
		int find = k;
		int pos = 1;
		int ans = 0;
		while (find > 0 && pos <= len) {
			for (int i = 0; i < 10; i++) {
				int h = this.howmany(ans, i, pos, len, high);
				if (find > h) {
					find -= h;
				} else {
					ans = ans * 10 + i;
					find -= 1;
					break;
				}
			}
			pos += 1;
		}
		return ans + find;
	}

	public int howmany(int head, int num, int pos, int len, int[] high) {
		if (num == 0 && pos == 1) {
			return 0;
		}
		int tmp = head * 10 + num;
		if (tmp > high[len]) {
			return 0;
		}
		int ans = 0;
		int basic = 10;
		for (int i = pos + 1; i < len; i++) {
			ans += basic;
			basic *= 10;
		}
		if (tmp < high[pos]) {
			ans += basic;
		} else if (tmp == high[pos] && high[len] - tmp * basic + 1 > 0) {
			ans += high[len] - tmp * basic + 1;
		}
		return ans + 1;
	}

	private int[] high(int n) {
		int[] stack = new int[11];
		int p = 0;
		while (n > 0) {
			stack[p++] = n % 10;
			n /= 10;
		}
		int i = 1;
		int[] ans = new int[p + 1];
		int num = 0;
		while (p > 0) {
			num = num * 10 + stack[--p];
			ans[i++] = num;
		}
		return ans;
	}

	private int len(int n) {
		int ans = 0;
		while (n > 0) {
			ans++;
			n /= 10;
		}
		return ans;
	}

	public static void main(String[] args) {
//		int max = (int) 1e9;
//		System.out.println(max);
		SolutionNew sn = new SolutionNew();
		int ans = sn.findKthNumber(1, 1);
		System.out.println(ans);
	}

}
